#快速排序
def solve(arr, L, R):
    if L >= R:
        return
    lt = L
    rt = R + 1
    #v分界点
    v = arr[L]
    i = L + 1
    while i < rt:
        #大于v
        if arr[i] > v:
            rt -= 1
            arr[i], arr[rt] = arr[rt], arr[i]
        #等于v
        elif arr[i] == v:
            i += 1
        #小于v
        else:
            arr[lt + 1], arr[i] = arr[i], arr[lt + 1]
            lt += 1
            i += 1
    arr[L], arr[lt] = arr[lt], arr[L]
    solve(arr, L, lt - 1)
    solve(arr, rt, R)


# arr = [4, 3, 6, 0, 1, 5, 4, 4, 5, 9 ,8 ,7 ,10, 4, 11, 15, 13, 12, 2, 3, -2, -7]
# solve(arr, 0, len(arr) - 1)
# print(arr)

#找中位数
def solve(arr1, arr2):
    length1 = len(arr1)
    length2 = len(arr2)
    if length1 > length2:
        solve(arr2, arr1)
    #特殊情况第一个数组为空
    if length1 == 0:
        #偶数情况
        if length2 % 2 == 0:
            return(arr2[length2 // 2] + arr2[length2 // 2 - 1]) / 2
            #奇数情况
        elif length2 % 2 == 1:
            return arr2[length2 // 2] / 0.5
    #利用二分查找思想
    result = 0 #中位数结果
    L = 0
    R = length1
    curA = 0
    curB = 0
    total = length1 + length2
    while L < R:
        curA = L
        curB = (total + 1) // 2 - curA
        L1 = -99999999 if curA == 0 else arr1[curA - 1]
        R1 = 99999999 if curA == length1 else arr1[curA]
        L2 = -99999999 if curB == 0 else arr2[curB - 1]
        R2 = 99999999 if curB == length2 else arr2[curB]
        #找线
        if L1 > R2: 
            R = curA - 1 #往前找小
        elif L2 > R1:
            L = curA + 1 #往后找大
        else: #找到了
            #偶数
            if total % 2 == 0:
                result = (max(L1, L2) + min(R1, R2)) / 2
            #奇数
            elif total % 2 == 1:
                result = max(L1, L2)
            break
    return result


arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8, 10]
print(solve(arr1,arr2))


